package org.example.SolutionNew006;

public class BinarySearch006 {
    public static void main(String[] args) {
        BinarySearch006 binarySearch006 = new BinarySearch006();
        int[] nums1=new int[]{1,2};
        int[] nums2=new int[]{3,4};
        System.out.println(binarySearch006.findMedianSortedArrays(nums1,nums2));

    }

    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        //可以合并，然后直接得到下标计算
        int[] merge=new int[nums1.length+nums2.length];
        int i=0,j=0,m=0;
        while(i<nums1.length && j<nums2.length){
            if(nums1[i]<=nums2[j]){
                merge[m++]=nums1[i++];
            }else{
                merge[m++]=nums2[j++];
            }
        }
        if(i<nums1.length){
            while(i<nums1.length){
                merge[m++]=nums1[i++];
            }
        }
        if(j<nums2.length){
            while(j<nums2.length){
                merge[m++]=nums2[j++];
            }
        }
        if(m%2==0){
            return (merge[m/2]+merge[m/2-1])/2.0;
        }else{
            return merge[m/2];
        }
    }

    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int n=nums1.length+nums2.length;
        int i=0,j=0,flag=-1;
        int time=n/2;
        int a=0,b=0;
        while(i<nums1.length && j<nums2.length && flag<time){
            flag++;
            a=b;
            if(nums1[i]<nums2[j]){
                b=nums1[i++];
            }else{
                b=nums2[j++];
            }
        }
        if(i<nums1.length && flag<time){
            while(i<nums1.length && flag<time){
                flag++;
                a=b;
                b=nums1[i++];
            }
        }
        if(j<nums2.length && flag<time){
            while(j<nums2.length && flag<time){
                flag++;
                a=b;
                b=nums2[j++];
            }
        }
        if(n%2==0){
            return (a+b)/2.0;
        }else{
            return b;
        }
    }

    public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int length1 = nums1.length,length2 = nums2.length;
        int n=length1+length2;
        if(n%2==1){
            int midNum=n/2+1;
            return findTheTarget(nums1,nums2,midNum);
        }else{
            int midNum=n/2;
            return (findTheTarget(nums1,nums2,midNum)+findTheTarget(nums1,nums2,midNum+1))/2.0;
        }
    }

    //midNum指第几个数
    public double findTheTarget(int[] nums1, int[] nums2, int k) {
        int index1=0,index2=0;
        while(true){
            //边界
            if(index1==nums1.length){
                return nums2[index2+k-1];
            }
            if(index2==nums2.length){
                return nums1[index1+k-1];
            }
            if(k==1){
                return Math.min(nums1[index1],nums2[index2]);
            }


            //正常
            int half=k/2;
            int nowIndex1=Math.min(index1+half,nums1.length)-1;
            int nowIndex2=Math.min(index2+half,nums2.length)-1;
            if(nums1[nowIndex1]<=nums2[nowIndex2]){
                k-=nowIndex1-index1+1;
                index1=nowIndex1+1;
            }else{
                k-=nowIndex2-index2+1;
                index2=nowIndex2+1;
            }
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length,length2 = nums2.length;
        if(length1>length2) return findMedianSortedArrays(nums2,nums1);
        int left=0,right=length1;
        int medium1=0,medium2=0;

        while(left<=right){
            int i=left+(right-left)/2;
            int j=(length1+length2+1)/2-i;

            int num_im1= i==0?Integer.MIN_VALUE:nums1[i-1];
            int num_i=  i==length1?Integer.MAX_VALUE:nums1[i];
            int num_jm1= j==0?Integer.MIN_VALUE:nums2[j-1];
            int num_j=  j==length2?Integer.MAX_VALUE:nums2[j];

            if(num_im1<=num_j){
                medium1=Math.max(num_im1,num_jm1);
                medium2=Math.min(num_i,num_j);
                left=i+1;
            }else{
                right=i-1;
            }
        }
        return (length1+length2)%2==1?medium1:(medium1+medium2)/2.0;
    }
}
